This code shows that small Baker-Luecke knots do not have Alexander polynomials in D.
##This is code that will search for an obtuse superbase
##in an integer CM lattice. Input is a list of
##coefficients for CM lattice.
#from itertools import combinations
#import numpy as np
import sympy as sp
import time
import math
def is_tight(sigma):
#Check whether a CM lattice has a tight index.
for i in range(1,len(sigma)):
if sigma[i]==1+ sum([sigma[j] for j in range(0,i)]):
return True
return False
def is_CM(sigma):
##Check the vector satisfies the CM condition
for i in range(1,len(sigma)):
if sigma[i]> 1+sum([sigma[j] for j in range(0,i)]):
return False
return True
def stable_is_decomposable(stable_coefs):
#Check whether any changemaker lattice associated to a set of stable
#coefficients can possibly be decomposable
stable=sorted(stable_coefs)
return is_decomposable([1]*stable[0]+stable)
def is_decomposable(sigma):
#Check whether a given changemaker lattice
#is decomposable.
##Uses Greene's algorithm of calculating the standard
##basis elements and checking that their intersection
##graph is connected.
if is_tight(sigma) or not is_CM(sigma):
return False
STD_basis=[]
n=len(sigma)
for i in range(1,n):
v=[0]*n
v[i]=-1
T=sigma[i]
j=i
while T>0:
j=max([k for k in range(0,j) if sigma[k]<=T])
v[j]=1
T-=sigma[j]
STD_basis.append(list(v))
S1=[STD_basis[0]]
S2=[]
for i in range(1,len(STD_basis)):
v=STD_basis[i]
flag=True
for w in S1:
if sum([v[j]*w[j] for j in range(0,n)])!=0:
flag=False
S1.append(list(v))
break
if flag:
S2.append(list(v))
if len(S2)==0:
return False
for v in S2:
for w in S1:
if sum([v[j]*w[j] for j in range(0,n)])!=0:
return False
return True
def norm(v):
return sum([z*z for z in v])
def irred_check(v,vtest):
#Computes T=(v-vtest).vtest returns true if this does not prove
#that v is reducible. I.e returns true if T<0 or vtest=0 or v=vtest.
T=sum([(v[i]-vtest[i])*vtest[i] for i in range(0,len(v))])
if T<0:
return True
if T==0:
if sum([z*z for z in vtest])==0:
return True
if sum([(v[i]-vtest[i])*(v[i]-vtest[i]) for i in range(0,len(v))])==0:
return True
return False
def vertex_bounds(sigma):
#Provide bounds on the coefficients of a vertex in
#in an OSB in a changemaker lattice.
n=len(sigma)
vmax=[0]*n
p=norm(sigma)
#Check if sigma is tight
vmax[0]=1
if is_tight(sigma):
vmax[0]=2
else:
vmax[0]=1
for i in range(1, len(sigma)):
if sigma[i]==sigma[i-1]:
vmax[i]=vmax[i-1]
continue
if sigma[i-1]==1 and sigma[i]>1:
vmax[i]=sigma[i]
continue
#If sigma[i] tight.
if sigma[i]> sum([sigma[j] for j in range(0,i)]):
vmax[i]=5+sum([vmax[j]+1 for j in range(0,i)])
else:
T=sigma[i]
j=i-1
while T>0:
j=max([k for k in range(0,j+1) if sigma[k]<=T])
vmax[i]=vmax[i]+vmax[j]+1
T-=sigma[j]
#Compute the bound coming from Cauchy-Schwartz inequality
for i in range(1,len(sigma)):
CS_bound= int(math.sqrt(p - sigma[i]*sigma[i]))
vmax[i]=min(CS_bound, vmax[i])
return vmax
def CM_generator(sigma, vmax):
##Iterates through all vectors in a changemaker lattice
##whose coordinates satisfy |v[i]|\leq vmax[i] for all i.
n=len(sigma)
v=[-vmax[i] for i in range(0,n)]
k=0
while True:
#Check whether there is a choice final coordinate to
#put vector in CM lattice. If so, yield that vector.
t= sum([sigma[i]*v[i] for i in range(0,n-1)])
if t%sigma[-1]==0:
v[-1]=-t//sigma[-1]
if v[-1]>=-vmax[-1] and v[-1]<=vmax[-1]:
yield v
#Now increment v.
while k<n-1 and v[k]+1>vmax[k]:
v[k]=-vmax[k]
k=k+1
if k<n-1:
v[k]+=1
k=0
else:
break
def list_vertices(sigma, quick=False):
##generate a list of candidate vertices with norm at least 3.
##If the quick flag is set to true, this does not
##generate precisely the set of all irreducibles.
##p=norm(sigma)
n=len(sigma)
irred_list=[]
#Vector defining the bounds on the search space
vmax=vertex_bounds(sigma)
#Modify vmax if we are doing a quick search
if quick:
vmax=[min(2, vmax[i]) for i in range(0,n)]
for i in range(0,n):
if sigma[i]==sigma[-1]:
vmax[i]=1
for v in CM_generator(sigma,vmax):
v_irred_flag=True
##Compare v against all other potential irreducibles.
if v_irred_flag:
for vtest in irred_list:
if irred_check(v,vtest)==False:
v_irred_flag=False
break
#if v is potentially irreducible, we use it filter out any
#non-irreducibles in irred_list and add it to irred_list.
if v_irred_flag:
irred_list=[w for w in irred_list if irred_check(w,v)]
irred_list+=[list(v)]
return irred_list
def half_int_OSB_search(sigma, quick=False):
##Given a changemaker vector search for an OSB for the corresponding
##n+1/2 changemaker lattice
p=2*norm(sigma)+1
n=len(sigma)
new_sigma=[0,1]+sigma
##populate potential obtuse superbases with known elements
initial_vertices=[[1,1,-1]+[0]*(n-1)]
k=1
while sigma[k]==1:
initial_vertices+=[[0]*(k+1)+[1,-1]+[0]*(n-k-1)]
k+=1
vertex_pool=[]
for z in list_vertices(sigma,quick):
z_new=[0,0]+z
##check z compatible with initial vertices
z_flag=True
for w in initial_vertices:
if sum([w[i]*z_new[i] for i in range(0,len(w))])>0:
z_flag=False
if z_flag:
vertex_pool+=[z_new]
#Now consider all possible combinations of vertices.
for t in obtuse_subsets(vertex_pool,n-len(initial_vertices)):
#print(t)
vertex_list=initial_vertices+list(t)
if obtuse_test(vertex_list,p):
return sp.Matrix(vertex_list)
return False
def int_OSB_search(sigma, quick=False):
##Search for an obtuse superbase. Function returns an OSB
#if it finds one. Returns false otherwise. The optional flag quick
##can be used to accelerate the search. When true the flag restricts
##the search of irreducibles to vectors with coefficients at most 2.
##Conjecturally, this is should still always find an OSB if it exists.
##However, we can only rigourously rule out the existence of
##an OSB if we run the algorithm with the quick flag set to False.
##This implementation is improved
## adding norm 2 vertices to the basis at the start
p=norm(sigma)
n=len(sigma)
#Create a list of norm 2 vectors that we will put in our basis.
norm2_vertices=[]
for i in range(1,n):
if sigma[i]==sigma[i-1]:
z=[0]*n
z[i]=1
z[i-1]=-1
norm2_vertices+=[list(z)]
#Filter our set of irreducibles by picking those with norm >2 and
#pairing 0 or -1 with the norm two vectors
vertex_pool=[]
for z in list_vertices(sigma,quick):
t=[sum([w[i]*z[i] for i in range(0,n)]) for w in norm2_vertices]
if len(t)==0 or (min(t)>=-1 and max(t)<=0):
vertex_pool+=[z]
#Now consider all possible combinations of vertices.
for t in obtuse_subsets(vertex_pool,n-len(norm2_vertices)-1):
vertex_list=norm2_vertices+list(t)
if obtuse_test(vertex_list,p):
return sp.Matrix(vertex_list)
return []
def obtuse_test(v_list, p):
##Check whether a given list of vectors forms an OSB for a lattice of discriminant p
n=len(v_list[0])
last_vertex=[sum(-v[k] for v in v_list) for k in range(n)]
if max(sum([v[i]*last_vertex[i] for i in range(n)]) for v in v_list)>0:
return False
M=sp.Matrix(v_list)
Q=M*(M.T)
for i in range(0,len(v_list)):
for j in range(i+1,len(v_list)):
if Q[i,j]>0:
return False
return Q.det()==p
def vertex_filter(v,w):
##function to decide if two vectors can appear
##in the same OSB.
return sum(v[i]*w[i] for i in range(len(v)))<=0
t=sum(v[i]*w[i] for i in range(len(v)))
return (t<=0 and t>-max(norm(v),norm(w)))
def obtuse_subsets(vertices, r):
##Given a list of vectors return subsets of size of r such all pairs
##satisfy v.w<=0. This is done via a breadth first search.
v=vertices
clist=[]
n=len(vertices)
for i in range(n):
clist+=[[j for j in range(i+1,n) if vertex_filter(v[i],v[j])]]
sols=[[i] for i in range(n)]
for k in range(r-1):
new_sols=[]
for sol in sols:
new_sols+= [sol + [j] for j in clist[sol[-1]]]
sols=list(new_sols)
#print(len(sols), sols)
for sol in sols:
yield [v[i] for i in sol]
def adhoc_tests(stable_coefs):
##Some tests for whether a given set of cable coefficients
##can possibly support an OSB. Returns false if there cannot
##exist an OSB. Returns true if inconclusive. These methods
##are not necessary they are simply used to accelerate running
##times.
stable=sorted(stable_coefs)
##If the stable coefficents contain 4,4,4,4,3,3,2 then
##there is no OSB.
if stable.count(4)>=4 and stable.count(3)>=2 and stable.count(2)>=1:
return False
##If the stable coefficents contain 3,3,3,3,2,2,2 then
##there is no OSB.
if stable.count(3)>=4 and stable.count(2)>=3:
return False
##The obstruction based on Corollary ?? from the paper.
for k in range(0,len(stable)-1):
N=stable.count(stable[k])
if N>=4 and (N-1)*stable[k]>stable[k+1]>stable[k]:
return False
return True
def verify_stable_in_D(stable_coefs, quick=False):
##Verify whether a given set of stable coefficients can come from
##the Alexander polynomial of a knot in D by searching the N-1/2
##changemaker lattice for an OSB.
stable=sorted(stable_coefs)
n=len(stable)
##Determine number of coefficients equal to one to get N-1 CM-vector
t= max([stable[k]-sum([stable[j] for j in range(0,k)]) for k in range(0,n)])
sigma=[1]*(t-1)+stable
if half_int_OSB_search(sigma,quick)==False:
return False
else:
return True
def find_OSB_slopes(stable_coefs):
##Input the stable coefficients. Returns a rigourously verified
##list of integer coefficients for which there is an OSB. Returns a
##list of slopes and an OSB in matrix form.
output=[]
if adhoc_tests(stable_coefs)==False:
return output
stable=sorted(stable_coefs)
##Check whether these stable coefficients support a decomposable lattice.
decomposable= stable_is_decomposable(stable)
slopes=[]
##Work out which slopes can conceivably admit an OSB.
if decomposable:
slopes=[0,1,2]
elif is_CM([1]*(stable[0]-1)+stable):
slopes=[0,1]
else:
slopes=[1,2]
#First perform a quick search to find OSBs with small coefficients.
for k in slopes:
sigma=[1]*k+[1]*(stable[0]-1)+stable
n=norm(sigma)
if is_CM(sigma):
##First run a quick search
result=int_OSB_search(sigma,quick=True)
if len(result)>0:
output+=[[n,result]]
else:
##If an OSB not found quickly, run a full search instead.
result=int_OSB_search(sigma, quick=False)
if len(result)>0:
output+=[[n,result]]
return output
# t_list=[[2],[3],[4], [2,2],[2,2,2],[3,2,2],[3,2,2,2]]
# p_list=[[12, 9, 5, 4, 2],
# [16, 12, 7, 4, 2],
# [18, 13, 7, 6, 2, 2],
# [17, 14, 5, 5, 4, 2],
# [26, 17, 12, 5, 4, 2]
# ]
# c_list=[[12, 9, 5, 4, 2],
# [16, 12, 7, 4, 2],
# [17, 14, 5, 5, 4, 2],
# [17, 13, 7, 6, 3],
# [18, 13, 7, 6, 2, 2],
# [26, 17, 12, 5, 4, 2],
# [23, 19, 7, 7, 4, 2],
# [23, 17, 10, 6, 3],
# [17, 17, 13, 7, 6, 3],
# [28, 12, 12, 7, 4, 2],
# [24, 18, 11, 6, 2, 2],
# [12, 12, 9, 5, 4, 2],
# [17, 17, 14, 5, 5, 4, 2],
# [18, 18, 13, 7, 6, 2, 2]
# ]
# import time
# start_time = time.time()
# for c in t_list:
# start_time=time.time()
# print(c)
# print(verify_stable_in_D(c,True))
# print("Example time: %f s" %(time.time()-start_time))
##Stable Coefficients:
##BL_knot:[1, 1, 1, 1, 0](0,0) [12, 9, 5, 4, 2]
##BL_knot:[1, 1, 0, 1, 1](0,0) [16, 12, 7, 4, 2]
##BL_knot:[1, 1, 1, 2, 0](0,0) [12, 12, 9, 5, 4, 2]
##BL_knot:[1, 1, 2, 1, 0](0,0) [17, 14, 5, 5, 4, 2]
##BL_knot:[1, 2, 1, 1, 0](0,0) [17, 13, 7, 6, 3]
##BL_knot:[2, 1, 1, 1, 0](0,0) [18, 13, 7, 6, 2, 2]
##BL_knot:[1, 1, 1, 1, 1](0,0) [26, 17, 12, 5, 4, 2]
##BL_knot:[1, 1, 0, 2, 1](0,0) [23, 19, 7, 7, 4, 2]
##BL_knot:[1, 2, 0, 1, 1](0,0) [23, 17, 10, 6, 3]
##BL_knot:[1, 1, 2, 2, 0](0,0) [17, 17, 14, 5, 5, 4, 2]
##BL_knot:[1, 2, 1, 2, 0](0,0) [17, 17, 13, 7, 6, 3]
##BL_knot:[2, 1, 1, 2, 0](0,0) [18, 18, 13, 7, 6, 2, 2]
##BL_knot:[1, 1, 0, 1, 2](0,0) [28, 12, 12, 7, 4, 2]
##BL_knot:[2, 1, 0, 1, 1](0,0) [24, 18, 11, 6, 2, 2]
BL_list=[[12, 9, 5, 4, 2],
[16, 12, 7, 4, 2],
[12, 12, 9, 5, 4, 2],
[17, 14, 5, 5, 4, 2],
[17, 13, 7, 6, 3],
[18, 13, 7, 6, 2, 2],
[26, 17, 12, 5, 4, 2],
[23, 19, 7, 7, 4, 2],
[23, 17, 10, 6, 3],
[17, 17, 14, 5, 5, 4, 2],
[17, 17, 13, 7, 6, 3],
[18, 18, 13, 7, 6, 2, 2],
[28, 12, 12, 7, 4, 2],
[24, 18, 11, 6, 2, 2]]
for stable in BL_list:
start_time=time.time()
print(stable)
print(verify_stable_in_D(stable,True))
print("Example time: %f s" %(time.time()-start_time))
[12, 9, 5, 4, 2] False Example time: 0.329038 s [16, 12, 7, 4, 2] False Example time: 0.559223 s [12, 12, 9, 5, 4, 2] False Example time: 5.472702 s [17, 14, 5, 5, 4, 2] False Example time: 4.803319 s [17, 13, 7, 6, 3] False Example time: 0.282121 s [18, 13, 7, 6, 2, 2] False Example time: 5.118518 s [26, 17, 12, 5, 4, 2] False Example time: 11.103709 s [23, 19, 7, 7, 4, 2] False Example time: 13.502366 s [23, 17, 10, 6, 3] False Example time: 0.531706 s [17, 17, 14, 5, 5, 4, 2] False Example time: 166.902848 s [17, 17, 13, 7, 6, 3] False Example time: 4.599586 s [18, 18, 13, 7, 6, 2, 2] False Example time: 143.677569 s [28, 12, 12, 7, 4, 2] False Example time: 11.058084 s [24, 18, 11, 6, 2, 2] False Example time: 16.205099 s